package com.neuedu.queue;

import java.util.Iterator;

/**                     环形数组实现队列
 * 指针的移动一定要 取%，因为这是环形数组(这样就不用考虑越界问题)
 * 对比普通数组，环形数组起点和终点更自由，不用考虑移动数据，直接移动指针就行。因为任意一个值，都可以作为头。(非常大的优点)
 * 数组的性能更优，可以充分利用局部性原理，cpu缓存
 * 通用计算索引下标 (cur + step) % length,例如：向前走3步，当前3. 6%5=1
 * @param <E>
 */
public class ArrayQueue<E> implements Queue<E> , Iterable<E> {

    //当头尾指针指向同一元素时，即为空。
    //尾指针的作用：赋值(指向目标索引,利用尾指针赋值 )   入队
    //头指针的作用：所指元素 出队
    private int head = 0;//头尾初始化都为0
    private int tail = 0;
    private final int length;
    private final E[] array;

    @SuppressWarnings("all")    //注解作用是 抑制警告
    public ArrayQueue(int capacity) {//因为需要留一个位置给尾指针使用
        this.length = capacity + 1;
        this.array = (E[]) new Object[length];
    }

    /**
     * (tail+1)%array.length;是防止索引越界了  例如 容量为5(索引为 0 1 2 3 4)
     *  当前tail=4，+1后应该从0开始，而不是5
     * @param value 待插入值
     * @return
     */


    @Override
    public boolean offer(E value) {
        if (isFull()){
            return false;
        }
        array[tail] = value;
        tail = (tail+1)% array.length;//添加完元素，向后移动尾指针。
        return true;
    }

    @Override
    public E poll() {
        if (isEmpty()){
            return null;
        }
        E value = array[head];
        head = (head + 1) % array.length;
        return value;
    }

    @Override
    public E peek() {
        if (isEmpty()){
            return null;
        }
        E value = array[head];
        return value;
    }


    /**
     * 判断空 和 满 ，头尾指针都会重复(指向同一元素)，所以加入了哨兵(这个哨兵专门给尾指针用)。
     * 尾指针+1 = 头指针(严谨来说 (tail+1)%数组长度=head )，证明数组满了
     * @return
     */


    @Override
    public boolean isEmpty() {
        return head == tail;
    }

    @Override
    public boolean isFull() {
        return (tail + 1)%length == head;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int cur = head;//指针
            @Override
            public boolean hasNext() {
                return cur != tail;
            }

            @Override
            public E next() {
                E value = array[cur];
                cur = (cur + 1)% array.length;
                return value;
            }
        };
    }
}
